//给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 
//
// 求在该柱状图中，能够勾勒出来的矩形的最大面积。 
//
// 
//
// 示例 1: 
//
// 
//
// 
//输入：heights = [2,1,5,6,2,3]
//输出：10
//解释：最大的矩形为图中红色区域，面积为 10
// 
//
// 示例 2： 
//
// 
//
// 
//输入： heights = [2,4]
//输出： 4 
//
// 
//
// 提示： 
//
// 
// 1 <= heights.length <=10⁵ 
// 0 <= heights[i] <= 10⁴ 
// 
//
// Related Topics 栈 数组 单调栈 👍 2579 👎 0


package leetcode.editor.cn;

// [84]柱状图中最大的矩形

import java.util.Stack;

public class LargestRectangleInHistogram_84 {
    public static void main(String[] args) {
        Solution solution = new LargestRectangleInHistogram_84().new Solution();
        solution.largestRectangleArea(new int[]{2, 1, 5, 6, 2, 3});
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int largestRectangleArea(int[] heights) {
            int[] arr = addZero(heights);
            Stack<Integer> stack = new Stack<>();
            stack.push(0);
            int ans = 0;
            for (int i = 1; i < arr.length; i++) {
                if (arr[i] > arr[stack.peek()]) {
                    stack.push(i);
                } else if (arr[i] == arr[stack.peek()]) {
                    stack.pop();
                    stack.push(i);
                } else {
                    while (!stack.isEmpty() && arr[i] < arr[stack.peek()]) {
                        int mid = stack.pop();
                        int h = arr[mid];
                        int w = i - stack.peek() - 1;
                        ans = Math.max(ans, h * w);
                    }
                    stack.push(i);
                }
            }
            return ans;
        }

        private int[] addZero(int[] arr) {
            int[] ans = new int[arr.length + 2];
            for (int i = 0; i < arr.length; i++) {
                ans[i + 1] = arr[i];
            }
            return ans;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}